#include <stdio.h>
#include <stdlib.h>

typedef unsigned int UINT;

// masklo 表示作斜方向上的冲突，maskvt 表示垂直方向上的冲突，maskro 表示右斜方向上的冲突, 行列坐标从0开始数
int nqueen(int num, UINT masklo, UINT maskvt, UINT maskro, int row, int col)
{
	if(row >= num)	return 1;
	if(col >= num) 	return 0;
	if((masklo | maskvt | maskro) & (1 << col))		// 如果有冲突
		return nqueen(num, masklo, maskvt, maskro, row, col + 1);	// 将尝试的位置移到下一列
	else
		// 计算新的 mask(模拟在这个位置放置棋子), 将尝试的位置移动到下一行第一列
		return nqueen(num, masklo, maskvt, maskro, row, col + 1) + 
			   nqueen(num, (masklo | (1 << col)) << 1, maskvt | (1 << col), (maskro | (1 << col)) >> 1, row + 1, 0);
}

int main(int argc, char *argv[])
{
	int n = 8;
	if(argc == 2)
		n = atoi(argv[1]);
	printf("%d\n", nqueen(n, 0, 0, 0, 0, 0));
	return 0;
}
